package AlgorithmStudy.study.track;

import java.util.*;

public class TraceBackTest {

    public static void main(String[] args) {
        List<List<Integer>> permute = permute(new int[]{1, 2, 3});
        System.out.println(permute.toString());
        // [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
    }

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> list = new ArrayList<Integer>();
        for(int n : nums){
            list.add(n);
        }

        int n = nums.length;
        traceback(n, list, res, 0);
        return res;
    }

    public static void traceback(int n, List<Integer> list, List<List<Integer>> res, int index){
        if(index==n){
            res.add(new ArrayList<Integer>(list));
        }
        for(int i=index; i<n; i++){
            // 交换
            Collections.swap(list, index, i);
            // 递归
            traceback(n, list, res, index+1);
            // 撤销交换
            Collections.swap(list, index, i);
        }
    }

}
